home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Mission 3
/
Mission 3.zip
/
Mission 3.iso
/
demovers
/
scripter
/
libs
/
sort.lib
< prev
Wrap
Text File
|
1998-09-26
|
1KB
|
74 lines
proc qsort(&arr, start, end, compare(&elem1, &elem2))
local up, down, pivot;
{
while (end > start) {
up = start;
down = end;
pivot = arr[(start + end) / 2];
do {
while (compare(arr[up], pivot) < 0) ++up;
while (compare(arr[down], pivot) > 0) --down;
if (up <= down) swap(arr[up++], arr[down--]);
} while (up <= down);
if (down - start > end - up) {
if (end > up) qsort(arr, up, end, compare);
end = down;
}
else {
if (down > start) qsort(arr, start, down, compare);
start = up;
}
}
}
proc qsort_array(&arr, compare(&elem1, &elem2))
{
qsort(arr, 0, arr.length - 1, compare);
}
proc lfind(&key, &array, max, compare(&elem1, &elem2))
local i;
{
if (max > array.length) max = array.length;
for (i = 0; i < max; ++i)
if(compare(array[i], key) == 0) return i;
return -1;
}
proc lsearch(&key, &array, &max, compare(&elem1, &elem2))
local idx;
{
if ((idx = lfind(key, array, max, compare)) < 0) {
if (array.length <= max) array.length = max + 1;
array[max++] = key;
return max - 1;
}
return idx;
}
proc bsearch(&key, &array, max, compare(&elem1, &elem2))
local min, idx, cval;
{
if (max > array.length) max = array.length;
--max;
min = 0;
while (min <= max) {
idx = (min + max) / 2;
if ((cval = compare(array[idx], key)) == 0) return idx;
if (cval > 0) max = idx - 1;
else min = idx + 1;
}
return -1;
}